МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Інститут економіки і менеджменту
Кафедра маркетингу і логістики
Лабораторна робота №2
з дисципліни «Економіко-математичні методи і моделі. Опитимізаційні методи і моделі»
на тему:
«Визначення оптимального рішення задачі
графічним методом»
Варіант 8
ВСТУП
Для розв’язування двовимірних задач лінійного програмування, тобто задач із двома змінними, а також деяких тривимірних задач застосовують графічний метод, що ґрунтується на геометричній інтерпретації та аналітичних властивостях задач лінійного програмування. Обмежене використання графічного методу зумовлене складністю побудови багатогранника розв’язків у тривимірному просторі (для задач з трьома змінними), а графічне зображення задачі з кількістю змінних більше трьох взагалі неможливе.
Для графічного розв’язання задачі лінійного програмування існують такі властивості:
якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин її багатокутника розв’язків;
якщо ж цільова функція досягає екстремального значення більш як в одній вершині багатокутника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією цих вершин.
Отже, розв’язати задачу лінійного програмування графічно означає знайти таку вершину багатокутника розв’язків, у результаті підстановки координат якої лінійна цільова функція набуває найбільшого (найменшого) значення.
Метою даної роботи є навчитись визначати оптимальні рішення задачі за допомогою графічного методу.
ЗАДАЧА:
Вихідні дані:
Побудувати та розв’язати графічно задачу лінійного програмування згідно варіанту. Дати економічну інтерпретацію результатам розв’язку.
Для виготовлення двох видів болтів А і Б завод використовує як сировину сталь і кольорові метали, запаси яких обмежені. На виготовлення вказаних двох виробів зайняті токарні і фрезерні верстати. У табл. 2.2 приведені вихідні дані. Визначити план випуску продукції, при якому буде досягнутий максимальний прибуток.
Таблиця 1
Норми витрат ресурсів та прибуток від реалізації готової продукції
Вид ресурсів
Обсяг ресурсів
Норми витрат на один виріб
Виріб А
Виріб Б
Сталь (т)
578
10
70
Кольорові метали (т)
428
20
50
Токарні верстати (станко-г)
5520
300
392
Фрезерні верстати (станко-г)
3320
208
100
Прибуток (тис.грн./т)
3
8
Математична модель задачі:
Цільова функція: S max = 3*x1+8*x2
Система обмежень: 10*x1+70*x2<=578 20*x1+50*x2<=428 300*x1+392*x2<=5520 208*x1+100*x2<=3320
Рішення задачі з використанням графічного симплекс-методу.
Побудуємо систему координат і проведемо прямі що обмежують область допустимих рішень (ОДР), побудувавши їх, відповідно, по нерівностях системи обмежень.
Щоб побудувати пряму потрібно знати координати двох точок. Координати точок прямих відповідних нерівностям:
Нерівність
X1
Y1
X2
Y2
10*x1+70*x2<=578
57,8
0
0
8,25714285714286
20*x1+50*x2<=428
21,4
0
0
8,56
300*x1+392*x2<=5520
18,4
0
0
14,0816326530612
208*x1+100*x2<=3320
15,9615384615385
0
0
33,2
Побудуємо вектор цільової функції S(3;8).
Система координат з областю допустимих рішень і вектором цільової функції зображена на рис.1.
/
Рис.1:Графік області допустимих рішень.
Як видно з графіка, мінімальною вершиною області допустимих значень буде вершина (1,17777777777778;8,08888888888889).
У даній вершині значення цільової функції рівне: S max = 3*1,17777777777778+8*8,08888888888889 = 68,2444444444445
ВИСНОВКИ:
На даній лабораторній роботі ми побудували та розв’язали графічно задачу лінійного програмування згідно варіанту, а також дали економічну інтерпретацію результатам розв’язку.
Для цього ми записали цільову функцію відповідно до варіанту, а саме S max = 3*x1+8*x2, а також встановили системи обмежень для цієї функції.
Відповідно нашим розрахункам, побудували графік області допустимих рішень задачі і мінімальну вершину області допустимих значень. У даній вершині...
